#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

//void AdjustDwon(HPDataType* a, int size, int parent)
//{
//	int child1 = 2 * parent + 1;
//	int child2 = 2 * parent + 2;
//
//	while (child1 < size && child2 < size)
//	{
//		if (a[child1] < a[child2])
//		{
//			if (a[child2] < a[parent])
//			{
//				swap(&a[child2], &a[parent]);
//				parent = child2;
//				child1 = 2 * child2 + 1;
//				child2 = 2 * child2 + 2;
//			}
//
//			else
//			{
//				break;
//			}
//		}
//
//		else
//		{
//			if (a[child1] < a[parent])
//			{
//				swap(&a[child1], &a[parent]);
//				parent = child1;
//				child2 = 2 * child1 + 2;
//				child1 = 2 * child1 + 1;
//
//			}
//
//			else
//			{
//				break;
//			}
//
//		}
//
//
//	}
//
//}

void test1()
{

	HP hp;
	HeapInit(&hp);

	int a[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };

	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		HeapPush(&hp,a[i]);
	}
	HeapPrint(&hp);

	HeapPush(&hp,10);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

}

void Print(int* a ,int n) 
{

	int i = 0;
	while (i<n)
	{
		printf("%d ", a[i++]);
		
	}
	printf("\n");
}

void test3(int* a,int n)
{
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a,n,i);
	}
	Print(a,n);

	int end = n - 1;

	while (end>0)
	{
		Swap(&a[0],&a[end]);
		AdjustDown(a,end,0);
		end--;
	}
    Print(a,n);

}


void test2()
{
	int a[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };

	test3(a,sizeof(a)/sizeof(a[0]));
}

//int main()
//{
//	//test1();
//	//test2();
//
//	char a[] = "abcdefg";
//	char b[5] = { 'a','b'};
//
//	//int j = 0;
//	//while (j)
//	//{
//	//	printf("%s ", a);
//	//	j++;
//	//}
//	//
//
//	//int i = 0;
//	//while (i)
//	//{
//	//	printf("%c ", * b[i] );
//	//}
//	//
//
//	////return 0;
//}


void PrintTopK(int* a, int n, int k)
{
	int* KMinHeap = (int*)malloc(sizeof(int) * k);


	for (int i = 0; i < k; i++)
	{
		KMinHeap[i] = a[i];
	}

	for (int i = (k - 2) / 2; i >= 0; i--)
	{
		AdjustDown(KMinHeap, k, i);
	}

	for (int j = k; j < n; j++)
	{
		if (KMinHeap[0] < a[j])
		{
			KMinHeap[0] = a[j];
			AdjustDown(KMinHeap, k, 0);
		}


	}

	for (int i = 0; i < k; ++i)
	{
		printf("%d ", KMinHeap[i]);
	}
	printf("\n");

}



void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (int i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[120] = 1000000 + 5;
	a[99] = 1000000 + 6;
	a[0] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);
}

int main()
{
	TestTopk();
	return 0;
}